package com.leetcode.algorithms.two.problem10;

import org.junit.Test;

/**
 * s could be empty and contains only lowercase letters a-z.
 * p could be empty and contains only lowercase letters a-z, and characters like . or *.
 */
public class RegularExpressionMatching {

    @Test
    public void run() {
        String s;
        String p;
        s = "ab";
        p = ".*c";
//        "a         b   b     a        b    aaaaaaa     c     aa"
//        "a*.*      b   .     a        .*               c*       a* "
//        "a*.*      b   .     a .* c*                       a*                         c*"

        System.out.println(isMatch(s, p));
    }

    /**
     * @param s string
     * @param p pattern
     * @return string 是否符合 pattern指定的格式
     */
    public boolean isMatch(String s, String p) {
        if (s == null && p == null)
            return true;
        if (s == null && p != null) {
            for (char c : p.toCharArray()) {
                if (c != '.' || c != '*')
                    return false;
            }
            return true;
        }
        if (s != null && p != null) {
            int index0 = 0;//s当前的index
            int i = 0;//p当前的index

            for (; i < p.length() - 1; i++) {
                char c1 = p.charAt(i);
                char c2 = p.charAt(i + 1);
                if (c2 == '*') {
                    //如果*是最后一个字符,比较当前符合就ok了
                    if (i + 2 == p.length()) {
                        if (c1 == '.')
                            return true;
                        else {
                            for (; index0 < s.length(); index0++) {
                                if (s.charAt(index0) != c1)
                                    return false;
                            }
                        }
                        return true;
                    } else {
                        for (; index0 <= s.length(); index0++) {
                            if(index0==s.length()){
                                if (isMatch(s.substring(index0), p.substring(i + 2)))
                                    return true;
                                break;
                            }
                            //如果p中  a*  能与s中的字符匹配  有可能匹配0个  有可能匹配多个
                            //匹配完之后只要剩下的p 和剩下的s有一个能匹配上就返回true
                            if (s.charAt(index0) == c1 || c1 == '.') {
                                if (isMatch(s.substring(index0), p.substring(i + 2)))
                                    return true;
                            } else {
                                //发现匹配不上的字符   结束这个循环,从*后面字符重新匹配
                                i = i + 1;
                                break;
                            }

                        }
                    }

                } else {
                    if (index0 > s.length() - 1 || (c1 != s.charAt(index0++) && c1 != '.'))
                        return false;
                }
//                if(c1=='.')
            }

            //比较最后一位
            if (s.length() - index0 == 1 && p.length() != 0) {
                if (p.charAt(i) == '.')
                    return true;
                if (p.charAt(i) == s.charAt(index0))
                    return true;
            }

            if(index0==s.length()&&i==p.length()){
                return true;
            }
        }

        return false;
    }


}
